from typing import List


class Solution:
    def maxmiumScore(self, cards: List[int], cnt: int) -> int:
        num0 = []
        num1 = []
        for card in cards:
            if card % 2 == 0:
                num0.append(card)
            else:
                num1.append(card)
        num0.sort()
        num1.sort()

        # 如果需要拿奇数张牌，则要拿一个偶数
        ans = 0
        if cnt % 2 == 1:
            if not num0:
                return 0
            ans += num0.pop()
            cnt -= 1

        while cnt > 0 and (len(num0) > 1 or len(num1) > 1):
            v1 = v2 = 0
            if len(num0) > 1:
                v1 = num0[-1] + num0[-2]
            if len(num1) > 1:
                v2 = num1[-1] + num1[-2]

            if v1 >= v2:
                ans += num0.pop()
                ans += num0.pop()
            else:
                ans += num1.pop()
                ans += num1.pop()

            cnt -= 2

        if cnt > 0:
            return 0

        return ans


if __name__ == "__main__":
    print(Solution().maxmiumScore(cards=[1, 2, 8, 9], cnt=3))  # 18
    print(Solution().maxmiumScore(cards=[3, 3, 1], cnt=1))  # 0

    # 自制用例
    print(Solution().maxmiumScore(cards=[1, 2, 2], cnt=3))  # 0
